Principe

Pour résoudre le problème précédent, une technique consister à placer un barrage sur la cellule du milieu pour ainsi diviser la zone de recherche en deux. Suivant l'endroit où se trouvait le monstre, on plaçait alors le barrage suivant au milieu de la zone du haut ou du bas, et ainsi de suite.

Cette méthode intuitive peut également être utilisée pour rechercher la valeur approchée d'une solution de certaines équations sur un intervalle.

L'algorithme de dichotomie est un algorithme permettant de déterminer une valeur approchée d'une solution d'une équation du type  `f(x)=0` en divisant l'intervalle de recherche par 2 à chaque itération.

Soit  `f` une fonction définie et continue sur un intervalle `[a;b]` . On suppose que  `f(a)` et  `f(b)` sont de signe contraire. Le théorème des valeurs intermédiaires assure alors de l'existence d'une solution à l'équation  `f(x)=0` sur l'intervalle  `[a;b]` .

On considère alors \(m=\dfrac{a+b}{2}\) . Deux cas de figure se présentent :

• soit \(f(a)\)  et \(f(m)\)  sont de signes contraires. Dans ce cas, l'équation  \(f(x)=0\) admet une solution sur l'intervalle \([a;m]\)  ;
• soit  \(f(b)\) et  \(f(m)\) sont de signes contraires. Dans ce cas, l'équation \(f(x)=0\)  admet une solution sur l'intervalle  \([m;b]\) .

On réitère alors le procédé en se plaçant sur l'intervalle  \([a;m]\) ou \([m;b]\) , selon le cas de figure.
Cette opération est alors répétée jusqu'à atteindre la précision désirée.